package C035;

import java.util.HashMap;
import java.util.HashSet;

/**
 * ClassName: C07
 * Package: C035
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/1/9 11:01
 * @Version 1.0
 * @Since 1.0
 */
public class C07 {
    public static void main(String[] args) {
        AllOne allOne = new AllOne();
        allOne.inc("hello");
        allOne.inc("hello");
        System.out.println(allOne.getMaxKey());
        System.out.println(allOne.getMinKey());
        allOne.dec("hello");
        allOne.dec("hello");
        System.out.println(allOne.getMaxKey());
        allOne.inc("hello");
        System.out.println(allOne.getMinKey());

        System.out.println("您好啊，安宣吉");
    }

}

class AllOne {

    class Bucket {
        int cnt;
        Bucket last;
        Bucket next;
        HashSet<String> set;

        public Bucket(int cnt, String str) {
            this.cnt = cnt;
            set = new HashSet<>();
            set.add(str);
        }
    }


    HashMap<String, Bucket> map = new HashMap<>();
    private Bucket head;
    private Bucket tail;

    public AllOne() {
        head = new Bucket(0, "");
        tail = new Bucket(Integer.MAX_VALUE, "");
        head.next = tail;
        tail.last = head;
    }

    public void inc(String key) {
        if (map.containsKey(key)) {
            Bucket bucket = map.get(key);
            if (bucket.next.cnt == bucket.cnt + 1) {
                bucket.set.remove(key);
                bucket.next.set.add(key);
                // 修改map的映射的对象
                map.put(key, bucket.next);
            } else {
                Bucket nextBuck = new Bucket(bucket.cnt + 1, key);
                setNext(bucket, nextBuck);
                bucket.set.remove(key);
                // 修改map的映射的对象
                map.put(key, bucket.next);
            }

            if (bucket.set.isEmpty()) {
                remove(bucket);
            }
        } else {
            if (head.next.cnt == 1) {
                head.next.set.add(key);
                map.put(key, head.next);
            } else {
                Bucket nextBuck = new Bucket(1, key);
                setNext(head, nextBuck);
                head.next.set.add(key);
                map.put(key, head.next);
            }
        }
    }

    // 删除节点
    private void remove(Bucket bucket) {
        Bucket last = bucket.last;
        Bucket next = bucket.next;
        last.next = next;
        next.last = last;
    }

    // 插入节点
    private void setNext(Bucket bucket, Bucket nextBuck) {
        Bucket next = bucket.next;
        bucket.next = nextBuck;
        next.last = nextBuck;
        nextBuck.next = next;
        nextBuck.last = bucket;
    }

    public void dec(String key) {
        if (!map.containsKey(key)) {
            return;
        }

        Bucket bucket = map.get(key);
        // 删除桶的元素
        bucket.set.remove(key);
        // 元素移到 次数-1 的桶
        if (bucket.last.cnt == bucket.cnt - 1) {
            bucket.last.set.add(key);
            // 更新map
            map.put(key, bucket.last);
        } else {
            Bucket lastBuck = new Bucket(bucket.cnt - 1, key);
            setNext(bucket.last, lastBuck);
            map.put(key, lastBuck);
        }
        if(bucket.set.isEmpty()) {
            remove(bucket);
        }
    }

    public String getMaxKey() {
        return tail.last.set.iterator().next();
    }

    public String getMinKey() {
        return head.next.set.iterator().next();
    }
}